package likou;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/08/12 20:03
 */
public class _516 {
    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("bbbab"));
    }
    public static int longestPalindromeSubseq(String s) {
        if (s == null) return 0;
        int len = s.length();
        char[] chs = s.toCharArray();
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        int max = 0;
        for (int i = len - 1; i >= 0; i--) {
            char cur = chs[i];
            //记录i、j之间（不包括i、j），回文串的最大值
            int curMax = 0;
            for (int j = i + 1; j < len; j++) {
                int mem = dp[j];
                if (cur == chs[j]) {
                    dp[j] = curMax + 2;//i的位置等于j的位置，则当前值需要变为（i~j之间的最大值）+2，这个2就是i与j的位置。
                }
                curMax = Math.max(mem, curMax);//记录最大值
            }
        }
        for (int e: dp) max = Math.max(max, e);
        return max;
    }
    public int longestPalindromeSubseq2(String s) {
        char[] cs = s.toCharArray();
        int len = s.length();
        int[] dp = new int[cs.length];
        Arrays.fill(dp,1);
        for(int i=len-1;i>=0;i--){
            char lc = cs[i];
            int cu = 0;
            for(int j=i+1;j<len;j++){
                int now = dp[j];
                char c = cs[j];
                if(c == lc){
                    dp[j] = 2 + cu;
                }
                cu = Math.max(now,cu);
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}
